La vista antes dada permite llegar a un modelo del
sistema operativo donde el nivel más bajo es el
planificador y el siguiente lo forman una variedad de procesos
(creados por los usuarios o partes del sistema
operativo).
0 | 1 | … | N -2 | N -1 |
Planificador | ||||
En el planificador no solo se considera el planificador
de procesos sino también los manejadores de
interrupción y la comunicación entre los
procesos.
La instrumentación efectiva del modelo de
procesos se logra mediante el uso de la tabla de procesos antes
explicada. Para tener una idea más precisa aún de
las informaciones contenidas en esta estructura (Fig2-4, pag. 50,
Tanembaun).
Programación
Concurrente. Grafos de precedencia.
El término programación concurrente o
simplemente concurrencia se refiere a la ejecución
paralela de instrucciones o procesos (aunque sea seudoparalela se
deberán tener en cuanta las mismas consideraciones).
Resulta conveniente revisar primero lo referente a las
instrucciones.
Suponga que se dispone de un procesador con varias
unidades funcionales para realizar las instrucciones o
simplemente se tienen múltiples CPU y se desean ejecutar
en grupo de instrucciones pertenecientes a un
programa.
S1: a = x + y;
S2: b = z + 1;
S3: c = a – b;
S4: w = c + 1;
Lógicamente la instrucción c = a – b no
puede ser ejecutada hasta que no hayan sido realizadas la S1 y la
S2 de forma tal que los valores de a y b hayan sido calculados.
Lo mismo ocurre con S4 con respecto a S3. En cambio las
instrucciones a = x + y, y b = z + 1 se pueden ejecutar
concurrentemente debido a que una no depende de la
otra.
Lo importante de notar en este ejemplo es que dentro de
un proceso existen restricciones de precedencia entre las
distintas instrucciones. Para esquematizar estas situaciones se
hace uso de los llamados grafos de precedencia.
Un grafo de precedencia es un grafo dirigido y sin
ciclos donde los nodos corresponden a instrucciones. Un arco
desde un nodo Si a un nodo Sj significa que la instrucción
Sj solo puede ser ejecutada después que se realice la
Si.
Por ejemplo, en las instrucciones antes indicadas se
tendría:
Otro ejemplo de grafo de precedencia podría
ser:
Condiciones de
concurrencia y especificación.
Para que dos instrucciones puedan ejecutarse
concurrentemente deberán cumplir ciertas condiciones. A
estas se le llaman condiciones de concurrencia.
Definamos el conjunto
R(Si) = {a1, a2, …, an} como el conjunto de
lectura para Si, este está formado por todas las variables
cuyos valores son referenciados en las instrucción Si
durante su ejecución.
Definamos el conjunto
W(Si) = {b1, b2, …, bm} como el conjunto de
escritura para Si, es decir todas las variables que cambian de
valor (se escriben) como resultado de la ejecución de la
instrucción Si.
Considerando la ecuación a = x + y se
tendrá:
R(Si) = {x, y} W(Si) = {a}
Si se toma la ecuación c = a – b
R(S3) = {a, b} W{S3) = {c}
Para que dos instrucciones sucesivas Sa y Sb puedan ser
ejecutadas concurrentemente y producir el mismo resultado se
tienen que cumplir las siguientes condiciones:
1.- R(Sa) ^ W(Sb) = {}
2.- R(Sb) ^ W(Sa) = {}
3.- W(Sa) ^ W(Sb) = {}
Si aplicamos estas condiciones a S1: a = x + y, y a S3:
c = a – b veremos que efectivamente ellas no pueden ejecutarse
concurrentemente ya que:
R(S3) ^ W(S1) = {a}
El grafo de precedencia es un medio útil para ver
las restricciones de precedencia que puedan existir en un
conjunto de instrucciones pertenecientes a un proceso, pero no
permiten presentar cálculos concurrentes en un lenguaje de
programación.
Las instrucciones fork and join fueron unas de las
primeras notaciones que se utilizaron para especificar en un
programa la ejecución concurrente de
instrucciones.
La instrucción fork L produce en un programa dos
hilos de ejecución concurrentes. Uno comienza en la
etiqueta L y el otro en la instrucción siguiente al
fork
La instrucción join permite unir o recombinar
varios hilos de ejecución en uno solo. Cada una de las
computaciones deben solicitar ser unidas con las otras. Dado que
cada hilo de ejecución debe ejecutar el join y lo realiza
en momentos diferentes, todos terminarán menos el
último. Debido a que el join necesita saber cuantos hilos
se deberán unir para poder terminar a todos menos el
último, la instrucción tiene un parámetro
con esta información.
El efecto de la instrucción join es como
sigue:
count = count – 1;
if (count ! = 0) quit;
donde quit es una instrucción que resulta en la
terminación de la ejecución. Ambas instrucciones se
ejecutan en forma indivisible.
A manera de ejemplos veamos los dos que se han utilizado
anteriormente .
count = 2; count1 = 2;
fork L1; count2 = 2;
a = x + y; S1;
go to L2; fork L1;
L1: b = z + 1; fork l2;
L2: join count; S2;
c = a – b; go to L3;
w = c + 1; L2:S3;
L3:join count2;
S5;
go to L4;
L1:S4;
L4:join count1;
S6;
La construcción fork-join tiene la desventaja de
no ser estructurada y por ello le son inherentes todas las
críticas que ha recibido el go to.
Una construcción estructurada para especificar
concurrencia es la parbegin / parend. Su forma es:
parbegin S1; S2 ; … ; Sn parend;
Todas la instrucciones encerradas entre parbegin y
parend se ejecutarán concurrentemente.
A manera de ejemplo veamos los dos anteriormente
utilizados con el fork y el join :
parbegin S1;
a = x + y; parbegin
b = z + 1; S4;
parend; {
c = a – b; parbegin
w = c + 1; S2;
S3;
parend;
S5;
}
parend;
S6;
Esta construcción estructurada tiene la
desventaja de que no puede especificar todos los grafos de
precedencia. No obstante, esta herramienta, unida con otros
mecanismos, si da una respuesta totalmente
satisfactoria.
Ahora es necesario extender los aspectos antes tratados,
en cuanto al uso de grafos de precedencia y las especificaciones
de programación, de instrucciones dentro de un proceso a
la relación entre procesos.
En este caso, cada nodo de un grafo de precedencia
será visto como un proceso secuencial. En tal ambiente los
procesos aparecen y desaparecen dinámicamente durante el
tiempo de duración de una ejecución.
Cuando un proceso Pi ejecuta una instrucción fork
L, se crea un proceso nuevo Pj. Al arribarse a la
instrucción join count, el contador es decrementado por
uno y si el resultado es cero, el proceso continua su
ejecución y en caso contrario terminará
.
Jerarquía
entre procesos.
Como ya se indicó con anterioridad un proceso
puede crear otros procesos. De igual forma los nuevos pueden
crear otros y así sucesivamente.
Para representar gráficamente este proceso de
creación sucesiva de procesos se utiliza el llamado grafo
de procesos que no es más que un árbol dirigido con
raíz . Un arco del nodo Pi al nodo Pj. En este caso se
dice que Pi es el padre de Pj o que Pj es hijo de Pi. Cada
proceso tiene un solo padre, pero tantos hijos como sean
necesarios.
Existen diversas formas en que un proceso puede crear
uno al hacer uso de una operación con este objetivo (como
la fork). Para ello se debe tener en cuenta como continúa
la ejecución y como se compartirán los
recursos.
Desde el punto de vista de como continúa la
ejecución se pueden instrumentar dos casos:
? El padre continúa la ejecución
concurrentemente con el hijo (construcción
fork/join).? El padre espera hasta que el hijo termina
(construcción parbegin/parend).
Desde el punto de vista de cómo se
compartirán los recursos se pueden instrumentar
también dos casos:
? El padre y el hijo comparten todas las
variables (construcción forK/join).? El hijo solo tiene acceso a un subconjunto de
las variables del padre (esquema del Unix).
Un proceso termina cuando ejecuta su última
instrucción, sin embargo existen circunstancias en que se
requiere terminarlo en forma forzada. Un proceso termina a otro
mediante una instrucción del tipo Kill Id.
La operación kill es usualmente invocada
solamente por un proceso padre para culminar la ejecución
de un hijo. Como la instrucción requiere la
identificación del proceso a ser terminado, la
instrucción fork da como retorno esta información
(Id = fork L). Existen numerosas razones por las cuales un padre
puede detener la ejecución de un hijo.
En muchos sistemas operativos se establece la
condición de que los procesos hijos no pueden continuar la
ejecución si el padre ha sido finalizado.
Un proceso que no termina su ejecución durante
todo el tiempo en que el sistema operativo está
funcionando se dice que es estático. Un proceso que
finaliza se dice que es dinámico.
Si un sistema operativo consiste de solo un
número limitado de procesos estáticos entonces su
correspondiente grafo de procesos será también
estático (es decir nunca cambia). En caso diferente
será dinámico. La estructura estática solo
está presente en sistemas operativos muy
simples.
La jerarquía de procesos antes discutida
está presente en la mayoría de los sistemas
operativos que soportan el modelo de procesos.
Para terminar veamos un ejemplo simple consistente de
dos procesos secuenciales que se ejecutan concurrentemente y que
comparten algunos datos en común. Este es un ejemplo
representativo de los sistemas de operación.
El ejemplo consiste en el clásico problema del
productor/consumidor. Un proceso productor genera
información que es tomada por el proceso consumidor. Por
ejemplo, un manejador de una impresora produce caracteres que son
consumidos por la impresoras.
Para permitir a los procesos productor y consumidor
ejecutarse concurrentemente se creará una piscina de
buffers. El productor generará en un buffer, mientas que
el consumidor tomará de otro buffer (si lo hicieran en el
mismo tendrían que correr secuencialmente).
El productor y el consumidor deberán ser
coordinados de forma tal que el consumidor no trate de consumir
elementos que aún no han sido producidos. En este caso, el
consumidor deberá esperar hasta que el elemento es
producido.
El problema que estamos tratando tiene dos formas de
presentarse: el primer caso consiste en fijar un límite
(diga menos n) en la cantidad de buffers disponibles en la
piscina, en segundo no se establece esta restricción y por
ello el productor siempre podrá generar nuevos elementos
(siempre habrá buffers vacíos).
La solución que se planteará estará
referida al primer caso y por ello el productor deberá
esperar cuando todos los buffers estén llenos.
La piscina de buffers compartida por ambos procesos se
instrumentará como un arreglo circular con dos punteros
lógicos: in y out. La variable in apunta al próximo
buffer libre, mientras out apunta al primer buffer
lleno.
Para controlar las condiciones extremas de todos los
buffers vacíos o llenos se podrían utilizar estas
dos posibilidades (in = out y in + 1 % n = out, respectivamente),
pero en este caso solo se permite que se puedan llenar hasta n –
1 buffers (se obliga a que exista uno vacío).
Para remediar esta dificultad se incorpora en la
solución un contador que originalmente recibe valor 0.
Esta variable se incrementará cada vez que se llene un
buffer de la piscina y decrementando cada vez que se consume uno
lleno de información.
/* Ejemplo de productor consumidor */
#define n 100
#define TRUE 1
typedef …item;
item buffer[n];
short int counter = 0, in = 0, out = 0;
void producir_elemento(punt_nextp)
item *punt_nextp;
{
.
.
.
}
void concumir_elemento(nextc)
item nextc;
{
.
.
.
}
void productor()
{
item nextp;
while (TRUE){
producir_elemento(&nextp);
while (counter= =n) skip;
buffer [in] = nextp;
in = (in+1) % n;
counter++;
}
}
void consumidor()
{
item nextc;
while (TRUE) {
while (counter = = 0) skip;
nextc = buffer[out];
out = (out+1) % n;
counter–;
consumir_elemento(nextc);
}
}
main()
{
parbegin
productor();
condumidor();
parend;
}
La instrucción skip no hace nada y por ello el
while se repite. Nótese que esta espera implica que se
continúe ejecutando aún cuando no se está
haciendo nada útil (espera ocupada).
La incorporación de las instrucciones parbegin y
parend se hacen con el objetivo de brindar la opción de
concurrencia.
Bibliografía:
? Operating System Concepts, Peterson y
Silberschatz, pag 103 – 110, pag 307-325.? Oprating Systems: Design and implementation,
Tanembaum, pag 45-51.
Autor:
Maikel J. Menendez
 Página anterior | Volver al principio del trabajo | Página siguiente  |